package pers.xuyong.strive.datastruct.tree;

/**
 * 二叉树
 *
 * @author billymac
 * @version 1.0
 * @date 17/8/7  下午2:26
 * @since JDK1.8
 */
public class BinaryTree extends AbstractTree implements Tree {

    public BinaryTree(double value) {
        this.root = new Node(this.lastInsertKey++, value);
    }

    public BinaryTree() {
    }

    /**
     * 以value值升序插入
     *
     * @param value
     * @return
     */
    @Override
    public boolean insert(double value) {
        if (root == null) {
            root = new Node(0, value);
            lastInsertKey ++;
        } else {
            Node temp = root;
            while (true) {
                double val = temp.value;
                if (val >= value) {
                    if(temp.leftNode == null) {
                        temp.leftNode = new Node(lastInsertKey++, value);
                        break;
                    } else {
                        temp = temp.leftNode;
                    }
                } else {
                    if(temp.rightNode == null) {
                        temp.rightNode = new Node(lastInsertKey++, value);
                        break;
                    } else {
                        temp = temp.rightNode;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 以key值升序插入
     * @param key
     * @param value
     * @return
     */
    @Override
    public boolean insert(int key, double value) {
        if (root == null)
            root = new Node(key, value);
        else {
            Node temp = root;
            while(true) {
                int k = temp.key;
                if (k >= key) {
                    if (temp.leftNode == null) {
                        temp.leftNode = new Node(key, value);
                        break;
                    } else {
                        temp = temp.leftNode;
                    }
                } else {
                    if (temp.rightNode == null) {
                        temp.rightNode = new Node(key, value);
                        break;
                    } else {
                        temp = temp.rightNode;
                    }
                }
            }
        }
        return true;
    }

    @Override
    public Node remove(int key) {
        return null;
    }

    /**
     * 查找节点
     *
     * @param value
     * @return
     */
    @Override
    public Node findNode(double value) {
        Node temp  = null;
        if(root != null) {
            Node tmp = root;
            while(true) {
                double val = tmp.value;
                if(val == value) {
                    temp = tmp;
                    break;
                } else if(val > value) {
                    if (tmp.leftNode == null)
                        break;
                    else
                        tmp = tmp.leftNode;
                } else {
                    if (tmp.rightNode == null)
                        break;
                    else
                        tmp = tmp.rightNode;
                }
            }
        }
        return temp;
    }

    @Override
    public Node findNode(int key) {
        Node temp = null;
        if (root != null) {
            Node tmp = root;
            while (true) {
                int k = tmp.key;
                if (k == key) {
                    temp = tmp;
                    break;
                } else if(k > key) {
                    if(tmp.leftNode == null)
                        break;
                    else
                        tmp = tmp.leftNode;
                } else {
                    if (tmp.rightNode == null)
                        break;
                    else
                        tmp = tmp.rightNode;
                }
            }
        }
        return temp;
    }

    @Override
    public void display(Node node) {
        if(node != null) {
            display(node.leftNode);
            node.display();
            display(node.rightNode);
        }
    }

    @Override
    public void leftDisplay(Node node) {
        if(node != null) {
            node.display();
            leftDisplay(node.leftNode);
            leftDisplay(node.rightNode);
        }
    }

    @Override
    public void rightDisplay(Node node) {
        if(node != null) {
            rightDisplay(node.leftNode);
            rightDisplay(node.rightNode);
            node.display();
        }
    }
}
